#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 배열은 index 1부터 정렬된다. (0은 무시) */

/* 
 * i를 루트로 해서 자식들을 포함하는 subtree가 힙 성질을 만족한다면
 * i를 포함하여 힙성질을 만족하도록 변환한다.
 */

 void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
 }
void adjust(int a[], int i, int n)
{
    int j, k, done;

    done=0;
    k=a[i]; //비교값 
    j=2*i; //자식
    while ((j<=n)&&(!done))     /* 자식노드가 있고 not done일 때까지 반복 */
    {
        // 둘 중 더 큰 자식을 고름
        if (j<n) {                 /* 오른쪽 자식노드가 존재하는가? (오른쪽 존재하면 왼쪽은 당연히 존재*/
            if (a[j]<a[j+1]) {       /* 자식노드들 중 큰 노드를 선택 */
                j=j+1;
            }
        }

        if (k>=a[j]) { /* 부모 노드의 크기가 자식보다 크다면 */
            done=1;        /* 자식노드보다 크므로 반복을 중단 */
        }
        else{
            a[j/2]=a[j]; /* 큰 자식의 값을 부모에 겹쳐 쓴다.(밀어내다가 끝나면 빈자리에 k를 넣음 */
            j=2*j;
        }
    }
    a[j/2]=k;
}

/*
 * 전체를 힙 구조로 바꾼 후 가장 큰 값을 --i로 보내고 계속 진행
 */

void heapsort(int key[], int n)
{
    int i, temp;

    for (i=(n/2);i>=1;--i) {      /* 초기 히프 만들기 */
        adjust(key, i, n);
    }

    for (i=(n-1);i>=1;--i /*처음 배열 들어갈때 이미 줄어들어 있음*/) {      /* 히프 정렬의 두 번째 단계 */
       
        /* i개의 키에 대하여 adjust 적용 */
        swap( &key[1], &key[i + 1]);
        adjust(key, 1, i);
    }
}


#define MAX 20
int main(int argc,char** argv) {
    int i,j;
    unsigned int array[MAX];
    unsigned int array_copy[MAX];
    array[i] = -1;
    for (i = 1; i < MAX; i++) {
        array[i] = rand()%30;
        array_copy[i] = array[i];
    }

    for (i = 0; i < MAX; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    heapsort(array, MAX-1);
    for (i = 0; i < MAX; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");


    // logic check routine
    for (i = 1; i < MAX; i++) {
        for (j = 1; j < MAX; j++) {
            if (array_copy[j] != -1) {
                if (array_copy[j] == array[i]) {
                    array_copy[j] = -1;
                    break;
                }
            }
        }
    }
    
    for (i = 1; i < MAX; i++) {
        if (array_copy[i] > -1) {
            printf("sort logic error!\n");
        }
    }
}
